#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;


//int find(vector<int> v, int a)
//{
//    if (a == v[a])
//        return v[a];
//    else
//        v[a] = find(v, v[a]);
//
//    return v[a];
//}
//void Union(vector<int>& v, int a, int b)
//{
//    int m1 = find(v, a);
//    int m2 = find(v, b);
//    v[m1] = v[m2];
//}
//int citys(vector<vector<int> >& m) {
//    // write code here
//    vector<int> v(201);
//    int ret = 1;
//    for (int k = 0; k < 201; k++)
//    {
//        v[k] = k;
//    }
//    int a = m.size();
//    int b = m[0].size();
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            if (m[i][j] == 1 && i != j)
//            {
//                Union(v, i, j);
//            }
//        }
//    }
//    int num = a > b ? a : b;
//    vector<int> arr;
//    int po = find(v, 0);
//    arr.push_back(po);
//    int flag = 0;
//    for (int l = 1; l < num; l++)
//    {
//        for (int i = 0; i < arr.size(); i++)
//        {
//            if (find(v, l) != arr[i])
//            {
//                flag = 1;
//            }
//            else
//            {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//        {
//            ret++;
//        }
//    }
//    return ret;
//}
//int main()
//{
//    vector<vector<int>> vv = { {1,1,0},{1,1,0},{0,0,1},{1,0,1} };
//    citys(vv);
//
//}
//using namespace std;
//int check(string s1, string s2)
//{
//    sort(s1.begin(), s1.end());
//    sort(s2.begin(), s2.end());
//    if (s1.compare(s2) == 0)
//    {
//        return 1;
//    }
//    else {
//        return 0;
//    }
//}
//int main() {
//    int num = 0;
//    int ret = 1;
//    cin >> num;
//    string s;
//    cin >> s;
//    num--;
//    vector<string> vs;
//    vs.push_back(s);
//    int flag = 1;
//    while (num--)
//    {
//        string s1;
//        cin >> s1;
//        for (int i = 0; i < vs.size(); i++)
//        {
//            if (check(s1, vs[i]) == 0)
//            {
//                flag = 1;
//            }
//            else {
//                flag = 0;
//                break;
//            }
//        }
//        if (flag == 1)
//        {
//            ret++;
//            vs.push_back(s1);
//        }
//    }
//    cout << ret;
//    return 0;
//}

//#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <string>
//#include <vector>
//using namespace std;
//#include <iostream>
//#include <string>
//#include <vector>
//#include <map>
//
//using namespace std;
//int main()
//{
//	vector<map<int, int>> mv;
//	map<int, int> m1;
//	m1[0]++;
//	m1[1]++;
//	mv.push_back(m1);
//	return 0;
//}
//int main() {
//    int num = 0;
//    int ret = 1;
//    cin >> num;
//    string s;
//    cin >> s;
//    vector<map<int, int>> mv(1);
//    int Size = 1;
//    for (auto i : s)
//    {
//        mv[0][i]++;
//    }
//    num--;
//    while (num--)
//    {
//        string s1;
//        cin >> s1;
//        map<int, int> m1;
//
//        for (auto j : s1)
//        {
//            m1[j]++;
//        }
//        for (auto k : s1)
//        {
//            int flag = 0;
//            for (int l = 0; l < Size; l++)
//            {
//                cout << mv[l][k] << ' ' << m1[k]<<endl;
//                if (mv[l][k] != m1[k])
//                {
//                    ret++;
//                    mv.push_back(m1);
//                    Size++;
//                    flag = 1;
//                    break;
//                }
//            }
//            if (flag == 1)
//            {
//                break;
//            }
//        }
//        m1.clear();
//    }
//    cout << ret;
//
//    return 0;
//}
//int longestPalindromeSubseq(string s) {
//    int a = s.size();
//    vector<vector<int>> dp(a + 1, vector<int>(a + 1, 0));
//    for (int i = a; i > 0; i--)
//    {
//        for (int j = i; j <= a; j++)
//        {
//            if (i == j)
//            {
//                dp[i][j] = 1;
//            }
//            else if (s[i - 1] == s[j - 1])
//            {
//                if (j - i == 1)
//                {
//                    dp[i][j] = 2;
//                }
//                else if (j - i > 1)
//                {
//                    dp[i][j] = dp[i + 1][j - 1] + 2;
//                }
//            }
//            else
//            {
//                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
//            }
//        }
//    }
//    for (int i = 0; i <= a; i++)
//    {
//        for (int j = 0; j <= a; j++)
//        {
//            cout << dp[i][j];
//        }
//        cout << endl;
//    }
//    return dp[1][a];
//}
//
//int main()
//{
//    string s = "bbbab";
//    longestPalindromeSubseq(s);
//    return 0;
//}

//
//int main() {
//    string s1, s2;
//    cin >> s1 >> s2;
//    int a = s1.size();
//    int b = s2.size();
//    int Max = 0;
//    int pre = 0;
//    int tail = 0;
//    for (int i = 0; i < a; i++)
//    {
//
//        //int num
//        for (int j = 0; j < b; j++)
//        {
//            int k = 0;
//            if (s2[j] == s1[i])
//            {
//                int num1 = i, num2 = j;
//                while (num1 < a && num2 < b && s1[num1] == s2[num2])
//                {
//                    num1++;
//                    num2++;
//                    k++;
//                }
//                if (k > Max)
//                {
//                    Max = k;
//                    pre = i;
//                    tail = num1 - 1;
//                }
//            }
//        }
//    }
//    if (tail == a - 1||pre==0)
//    {
//        int c = b - a;
//        cout << b - Max - c;
//    }
//    else {
//        cout << b - Max;
//    }
//    return 0;
//}
//#include <iostream>
//#include <string>
//#include <vector>
//#include <set>
//using namespace std;
//
//
//int main() {
//    int num = 0;
//    cin >> num;
//    set<long long> s;
//    long long Max = 0;
//    for (int i = 0; i < num; i++)
//    {
//        long long a = 0;
//        cin >> a;
//        Max = max(a, Max);
//        s.insert(a);
//    }
//    
//    while (s.size() != 1)
//    {
//        if (*(s.begin()) == Max)
//        {
//            cout << "NO";
//            return 0;
//        }
//        long long a = *(s.begin());
//        s.erase(a);
//        s.insert(2 * a);
//    }
//    cout << "YES";
//    return 0;
//}
//int main()
//{
//	vector<int> v{ 1,2,5,3,9 };
//	set<int> s;
//	for (auto i:v)
//	{
//		s.insert(i);
//	}
//	for (auto j : s)
//	{
//		cout << j << endl;
//	}
//
//	return 0;
//}

//int main() {
//    string s;
//    cin >> s;
//    int a = s.size();
//    vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1));
//    for (int i = a; i >= 0; i--)
//    {
//        for (int j = i; j <= a; j++)
//        {
//            if (i == j)
//            {
//                cout << dp[i][j] << ' ';
//
//                dp[i][j] == 1;
//                break;
//            }
//            if (s[i - 1] == s[j - 1])
//            {
//                dp[i][j] = j - i == 1 ? 1 : dp[i + 1][j - 1];
//            }
//            cout << dp[i][j] << ' ';
//        }
//        cout << endl;
//    }
//    //cout<<dp[a][a];
//
//    return 0;
//}